/* Copyright 2009 Anthony Surma
This file is part of Java's Kademlia Extension (JKADX).

JKADX is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
any later version.

JKADX is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with JKADX.  If not, see <http://www.gnu.org/licenses/>.
*/

package jkadx.dht;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock.ReadLock;
import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock;

/**
 * @author Anthony Surma
 */
public final class KBucket
{
    public    final static int                 K                = 20;
    private   final static boolean             IF_NOT_LOCKED    = false;
    private   final static boolean             THEN_LOCK_IT     = true;   
    public    final static String              SEPERATOR        = "#";
    private   final        LinkedList<Contact> kBucketList;
    private   final        LinkedList<Contact> replaceList;
    private   final        ReadLock            kBucketRead;
    private   final        WriteLock           kBucketWrite;
    private   final        WriteLock           replaceListWrite;
    private   final        ReadLock            replaceListRead;
              final        int                 maxSize;
    private   volatile     boolean             isFull     = false;
              volatile     boolean             isEmpty    = true;
    @Testing  final static AtomicInteger       discarded  = new AtomicInteger(0);
    @Testing  final static AtomicInteger       updated    = new AtomicInteger(0);
    @Testing  final static AtomicInteger       addedEqual = new AtomicInteger(0);
        
    KBucket(final int position)
    {
        final ReentrantReadWriteLock kBucketReentrant = new ReentrantReadWriteLock();
        final ReentrantReadWriteLock ReplaceReentrant = new ReentrantReadWriteLock();

	this.kBucketRead      = kBucketReentrant.readLock();
	this.kBucketWrite     = kBucketReentrant.writeLock();
        this.replaceListRead  = ReplaceReentrant.readLock();
	this.replaceListWrite = ReplaceReentrant.writeLock();
	this.kBucketList      = new LinkedList<Contact>();
        this.replaceList      = new LinkedList<Contact>();

	if      (position == UniqueId.NBITS - 1) maxSize =  1;
        else if (position == UniqueId.NBITS - 2) maxSize =  2;
        else if (position == UniqueId.NBITS - 3) maxSize =  4;
        else if (position == UniqueId.NBITS - 4) maxSize =  8;
        else if (position == UniqueId.NBITS - 5) maxSize = 16;
        else maxSize = DHT.K;
    }

    @Override
    public String toString()
    {
	final StringBuilder result = new StringBuilder();

	kBucketRead.lock();	
	for (Contact c : kBucketList)
	{
            result.append(c);
            result.append(SEPERATOR);
	}	
	kBucketRead.unlock();
	return result.toString();
    }

    Contact updateIfEqualMatchElseAddIfNotFull(final Contact thisContact) //XXX too complicated
    {
	ListIterator<Contact> iterator;
	Contact               current;
	LinkedList<Contact>   kBucketList  = this.kBucketList;
	ReadLock              kBucketRead  = this.kBucketRead;
	WriteLock             kBucketWrite = this.kBucketWrite;

	kBucketRead.lock();
	iterator = kBucketList.listIterator();
	while (iterator.hasNext())
	{
	    current = iterator.next();
	    if (current.uniqueId.matches(thisContact.uniqueId)) // check if it already exists... found same nodeid
	    {
		if (current.matchesSocketAddress(thisContact)) // port and ipaddress match
		{
		    if (current.isLocked.compareAndSet(IF_NOT_LOCKED, THEN_LOCK_IT))
		    {                      
			kBucketRead.unlock();
                        kBucketWrite.lock();
			 // another thread might have changed order of list just before here...
			kBucketList.remove(current); // .. so can't reuse iterator at this point, unfortunately
                        //if (kBucketList.contains(current)) addedEqual.incrementAndGet();
                        kBucketList.add(current); // update position in list
                        current.isLocked.lazySet(false);
			updated.incrementAndGet();
			kBucketWrite.unlock();
			return null; // winner
		    }
		    else // it was already locked
		    {
			discarded.incrementAndGet(); //added
			kBucketRead.unlock();
			return null; // this thread is the loser
		    }
		}
		else // equals, but ipaddress and/or port don't match
		{                   
		    if (current.isLocked.compareAndSet(IF_NOT_LOCKED, THEN_LOCK_IT))
		    {
			kBucketRead.unlock();
			return current; // winner
		    }
		    else // it was already locked
		    {
			discarded.incrementAndGet();
			kBucketRead.unlock();
			return null; // loser
		    }
		}
	    }
	}       
	if (!isFull())
	{            
	    kBucketRead.unlock();
	    kBucketWrite.lock();
            // time may pass between locks, so need to check if another thread added it
            iterator = kBucketList.listIterator();
            while (iterator.hasNext())
            {
                current = iterator.next();
                if (current.uniqueId.matches(thisContact.uniqueId)) // check if it already exists... found same nodeid
                {
                    if (current.matchesSocketAddress(thisContact)) // port and ipaddress match
                    {
                        if (current.isLocked.compareAndSet(IF_NOT_LOCKED, THEN_LOCK_IT))
                        {
                            iterator.remove(); 
                            //if (kBucketList.contains(current)) addedEqual.incrementAndGet();
                            kBucketList.add(thisContact); // update position in list
			    //updated.incrementAndGet();
                            //current.isLocked.set(false);
			    kBucketWrite.unlock();
			    return null; // winner
                        }
                        else // it was already locked
                        {
                            discarded.incrementAndGet(); //added
                            kBucketWrite.unlock();
                            return null; // this thread is the loser
                        }
                    }
                    else // equals, but ipaddress and/or port don't match
                    {
                        //equalContactThatDoesNotMatch.incrementAndGet();
                        if (current.isLocked.compareAndSet(IF_NOT_LOCKED, THEN_LOCK_IT))
                        {
                            kBucketWrite.unlock();
                            return current; // winner
                        }
                        else // it was already locked
                        {
                            discarded.incrementAndGet();
                            kBucketWrite.unlock();
                            return null; // loser
                        }
                    }
                }
            }
            // time may have passed between locks, so need to check if it's full now...
	    if (!isFull()) 
	    {
                //if (kBucketList.contains(thisContact)) addedEqual.incrementAndGet();
		kBucketList.add(thisContact);		
		isEmpty = false;
                kBucketWrite.unlock();
		return null; // winner, but losers can still try and replace an older contact
	    }            
            kBucketRead.lock(); // this order of locks is perfect, and safe.
	    kBucketWrite.unlock();
	}	        
	iterator = kBucketList.listIterator(); // we always have a kBucketRead at this point
	while (iterator.hasNext())
	{
	    current = iterator.next();
	    if (current.isLocked.compareAndSet(IF_NOT_LOCKED, THEN_LOCK_IT))
	    {
                replaceListWrite.lock(); // shouldn't *have* to do locks in this order
                kBucketRead.unlock();
               
                Contact curr;                
                iterator = replaceList.listIterator();
                while (iterator.hasNext())
                {
                    curr = iterator.next();
                    if (curr.uniqueId.matches(thisContact.uniqueId))
                    {
                       current.isLocked.set(false);
                       replaceListWrite.unlock();
                       discarded.incrementAndGet(); // already being replaced
                       return null;
                    }
                }
                replaceList.add(thisContact);
                replaceListWrite.unlock();
		return current; // winner (this one is the problem)
	    }	    
	}
	discarded.incrementAndGet(); // all contacts are locked, so give up
	kBucketRead.unlock();
	return null; // loser
    }

    boolean replace(final Contact contactToReplace, final Contact newContact)
    {        
	kBucketWrite.lock();       
	if (kBucketList.remove(contactToReplace)) // this thread should always be the one that locked it
	{          
           //if (kBucketList.contains(contactToReplace)) System.out.println("hey"); //addedEqual.incrementAndGet();
            kBucketList.add(newContact);
	    kBucketWrite.unlock();
            replaceListRead.lock();
            if (replaceList.contains(newContact))
            {
                replaceListRead.unlock();
                replaceListWrite.lock();
                replaceList.remove(newContact);
                replaceListWrite.unlock();
            }
            else
            {
                replaceListRead.unlock();
            }
	    return true;
	}
	else
	{
	    kBucketWrite.unlock();
	    System.out.println("replaceIfKnown(): Should never see this, except for one test in TestKBucket");
	    return false;
	}
    }

    boolean update(final Contact existingContact, final Contact discarded)
    {         
	kBucketWrite.lock();
	if (kBucketList.remove(existingContact)) // this thread should always be the one that locked it
	{       
           // if (kBucketList.contains(existingContact)) addedEqual.incrementAndGet();
            kBucketList.add(existingContact);
	    existingContact.isLocked.lazySet(false);
	    kBucketWrite.unlock();
            replaceListRead.lock();
            if (replaceList.contains(discarded))
            {
                replaceListRead.unlock();
                replaceListWrite.lock();
                replaceList.remove(discarded);
                replaceListWrite.unlock();
            }
            else
            {
                 replaceListRead.unlock();
            }
	    return true;
	}
	else
	{
	    kBucketWrite.unlock();
	    System.out.println("updateIfKnown(): Should never see this, except for one test in TestKBucket");
	    return false;
	}
    }

    protected Contact[] sortByDistanceTo(final UniqueId targetId)
    {
        final Contact[] sorted;

	kBucketRead.lock();
	sorted = kBucketList.toArray(new Contact[0]);
	kBucketRead.unlock();


	ContactByDistance cbd = new ContactByDistance(targetId);
	Arrays.sort(sorted, cbd);
	return sorted;
    }

    boolean isFull()
    {
	if (isFull)
	    return true;
	else if (isEmpty)
	    return false;
	kBucketRead.lock();
	if (kBucketList.size() == maxSize)
	    isFull = true;	
	kBucketRead.unlock();
	return isFull;
    }

    int getSize()
    {
	if (isFull)	
	    return maxSize;
	else if (isEmpty)
	    return 0;	
	kBucketRead.lock();
	int size = kBucketList.size();
        kBucketRead.unlock();
	if (size == maxSize)	
	    isFull = true;		
	return size;
    }
    
    @Testing int getSizeTest()
    {
        int size;

        kBucketRead.lock();
	size = kBucketList.size();
	if (size == maxSize)	
	    isFull = true;	
	kBucketRead.unlock();
	return size;
    }

    @Testing int getNumContactsLocked()
    {
        int size = 0;

        kBucketRead.lock();
        for (Contact c : this.kBucketList)        
            if (c.isLocked.get())
                size++;
        kBucketRead.unlock();
        return size;
    }

    @Testing int getSizeOfReplaceListTest()
    {
        int size;

	replaceListRead.lock();
	size = replaceList.size();
	replaceListRead.unlock();
	return size;
    }
}